#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
using namespace std;

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i=0;
        int small = abs(nums[0]);
        while(k>0 && i<nums.size() && nums[i]<=0){
            nums[i]=-nums[i];
            small = min(small, nums[i]);
            ++i;
            --k;
        }if(i<nums.size())small = min(small, nums[i]);
        int sum = 0;
        for(int i=0; i<nums.size(); ++i) sum+=nums[i];
        if(k>0 && k&1){
            sum-=(small<<1);
        }
        return sum;
    }
};